home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DJGPP / LGP250S1.ZIP / src / libgplus.5 / libgplus / tests / tset.cc < prev    next >
C/C++ Source or Header  |  1993-06-06  |  18KB  |  744 lines
  1. /*
  2.  a test file for sets
  3. */
  4.  
  5. #ifdef PTIMES
  6. const int ptimes = 1;
  7. #else
  8. const int ptimes = 0;
  9. #endif
  10.  
  11. #include <stream.h>
  12. #include <assert.h>
  13. #include <builtin.h>
  14.  
  15. #define tassert(ex) { cerr << #ex; \
  16.                        if ((ex)) cerr << " OK\n"; \
  17.                        else cerr << " Fail\n"; }
  18.  
  19. unsigned int hash(int x) { return multiplicativehash(x) ; }
  20.  
  21. #include "iSet.h"
  22.  
  23. int SIZE;
  24.  
  25. int *nums;
  26. int *odds;
  27. int *dups;
  28.  
  29. void printset(intSet& a)
  30. {
  31.   int maxprint = 20;
  32.   cout << "[";
  33.   int k = 0;
  34.   for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k) 
  35.     cout << a(i) << " ";
  36.   if (i != 0) cout << "...]\n";
  37.   else cout << "]\n";
  38. }
  39.  
  40. void add(int x[], intSet& a)
  41. {
  42.   for (int i = 0; i < SIZE; ++i) a.add(x[i]);
  43. }
  44.  
  45. #include <MLCG.h>
  46.  
  47. MLCG randgen;
  48.  
  49. void permute(int x[])
  50. {
  51.   for (int i = 1; i < SIZE; ++i)
  52.   {
  53.     int j = randgen.asLong() % (i + 1);
  54.     int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  55.   }
  56. }
  57.  
  58.  
  59. void makenums()
  60. {
  61.   for (int i = 0; i < SIZE; ++i) nums[i] = i + 1; 
  62. }
  63.  
  64. void makeodds()
  65. {
  66.   for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
  67.   permute(odds);
  68. }
  69.  
  70. void makedups()
  71. {
  72.   for (int i = 0; i < SIZE; i += 2) dups[i] = dups[i+1] = i/2 + 1;
  73.   permute(dups);
  74. }
  75.                
  76.  
  77. void generictest(intSet& a, intSet& b, intSet& c)
  78. {
  79.   c.clear();
  80.   assert(c.empty());
  81.   c |= a;
  82.   assert(c == a);
  83.   assert(c <= a);
  84.   c.del(a(a.first()));
  85.   assert(c <= a);
  86.   assert(c != a);
  87.   Pix i = a.first();
  88.   assert(!c.contains(a(i)));
  89.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  90.   c.add(a(a.first()));
  91.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  92.   c |= b;
  93.   assert(b <= c);
  94.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  95.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  96.   c &= a;
  97.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  98.   c -= a;
  99.   assert(!(a <= c));
  100.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  101.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  102.   assert(c.empty());
  103.   assert(a.OK());
  104.   assert(b.OK());
  105.   assert(c.OK());
  106. }
  107.  
  108. #include "iXPSet.h"
  109.  
  110. void XPtest()
  111. {
  112.   intXPSet a(SIZE);
  113.   add(nums, a);
  114.   assert(a.length() == SIZE);
  115.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  116.   intXPSet b(SIZE);
  117.   add(odds, b);
  118.   assert(b.length() == SIZE);
  119.   intXPSet c(SIZE);
  120.   add(dups, c); 
  121.   assert(c.length() == SIZE/2);
  122.   assert(c <= a);
  123.   intXPSet d(a);
  124.   d &= b;
  125.   cout << "a: "; printset(a);
  126.   cout << "b: "; printset(b);
  127.   cout << "c: "; printset(c);
  128.   cout << "d: "; printset(d);
  129.   assert(d.length() == SIZE/2);
  130.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  131.   a.del(1);
  132.   assert(a.length() == SIZE-1);
  133.   assert(!a.contains(1));
  134.  
  135.   c.clear();
  136.   assert(c.empty());
  137.   c |= a;
  138.   assert(c == a);
  139.   assert(c <= a);
  140.   c.del(a(a.first()));
  141.   assert(c <= a);
  142.   assert(c != a);
  143.   Pix i = a.first();
  144.   assert(!c.contains(a(i)));
  145.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  146.   c.add(a(a.first()));
  147.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  148.   c |= b;
  149.   assert(b <= c);
  150.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  151.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  152.   c &= a;
  153.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  154.   c -= a;
  155.   assert(!(a <= c));
  156.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  157.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  158.   assert(c.empty());
  159.   assert(a.OK());
  160.   assert(b.OK());
  161.   assert(c.OK());
  162.  
  163.   generictest(a, b, c);
  164. }
  165.  
  166.  
  167. #include "iSLSet.h"
  168.  
  169. void SLtest()
  170. {
  171.   intSLSet a;
  172.   add(nums, a);
  173.   assert(a.length() == SIZE);
  174.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  175.   intSLSet b;
  176.   add(odds, b);
  177.   assert(b.length() == SIZE);
  178.   intSLSet c;
  179.   add(dups, c); 
  180.   assert(c.length() == SIZE/2);
  181.   assert(c <= a);
  182.   intSLSet d(a);
  183.   d &= b;
  184.   cout << "a: "; printset(a);
  185.   cout << "b: "; printset(b);
  186.   cout << "c: "; printset(c);
  187.   cout << "d: "; printset(d);
  188.   assert(d.length() == SIZE/2);
  189.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  190.   a.del(1);
  191.   assert(a.length() == SIZE-1);
  192.   assert(!a.contains(1));
  193.  
  194.   c.clear();
  195.   assert(c.empty());
  196.   c |= a;
  197.   assert(c == a);
  198.   assert(c <= a);
  199.   c.del(a(a.first()));
  200.   assert(c <= a);
  201.   assert(c != a);
  202.   Pix i = a.first();
  203.   assert(!c.contains(a(i)));
  204.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  205.   c.add(a(a.first()));
  206.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  207.   c |= b;
  208.   assert(b <= c);
  209.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  210.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  211.   c &= a;
  212.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  213.   c -= a;
  214.   assert(!(a <= c));
  215.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  216.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  217.   assert(c.empty());
  218.   assert(a.OK());
  219.   assert(b.OK());
  220.   assert(c.OK());
  221.  
  222.   generictest(a, b, c);
  223. }
  224.  
  225.  
  226. #include "iVHSet.h"
  227.  
  228. void VHtest()
  229. {
  230.   intVHSet a(SIZE);
  231.   add(nums, a);
  232.   assert(a.length() == SIZE);
  233.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  234.   intVHSet b(SIZE);
  235.   add(odds, b);
  236.   assert(b.length() == SIZE);
  237.   intVHSet c(SIZE);
  238.   add(dups, c); 
  239.   assert(c.length() == SIZE/2);
  240.   assert(c <= a);
  241.   intVHSet d(a);
  242.   d &= b;
  243.   cout << "a: "; printset(a);
  244.   cout << "b: "; printset(b);
  245.   cout << "c: "; printset(c);
  246.   cout << "d: "; printset(d);
  247.   assert(d.length() == SIZE/2);
  248.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  249.   a.del(1);
  250.   assert(a.length() == SIZE-1);
  251.   assert(!a.contains(1));
  252.  
  253.   c.clear();
  254.   assert(c.empty());
  255.   c |= a;
  256.   assert(c == a);
  257.   assert(c <= a);
  258.   c.del(a(a.first()));
  259.   assert(c <= a);
  260.   assert(c != a);
  261.   Pix i = a.first();
  262.   assert(!c.contains(a(i)));
  263.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  264.   c.add(a(a.first()));
  265.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  266.   c |= b;
  267.   assert(b <= c);
  268.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  269.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  270.   c &= a;
  271.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  272.   c -= a;
  273.   assert(!(a <= c));
  274.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  275.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  276.   assert(c.empty());
  277.   assert(a.OK());
  278.   assert(b.OK());
  279.   assert(c.OK());
  280.  
  281.   generictest(a, b, c);
  282. }
  283.  
  284. #include "iVOHSet.h"
  285.  
  286. void VOHtest()
  287. {
  288.   intVOHSet a(SIZE);
  289.   add(nums, a);
  290.   assert(a.length() == SIZE);
  291.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  292.   intVOHSet b(SIZE);
  293.   add(odds, b);
  294.   assert(b.length() == SIZE);
  295.   intVOHSet c(SIZE);
  296.   add(dups, c); 
  297.   assert(c.length() == SIZE/2);
  298.   assert(c <= a);
  299.   intVOHSet d(a);
  300.   d &= b;
  301.   cout << "a: "; printset(a);
  302.   cout << "b: "; printset(b);
  303.   cout << "c: "; printset(c);
  304.   cout << "d: "; printset(d);
  305.   assert(d.length() == SIZE/2);
  306.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  307.   a.del(1);
  308.   assert(a.length() == SIZE-1);
  309.   assert(!a.contains(1));
  310.  
  311.   c.clear();
  312.   assert(c.empty());
  313.   c |= a;
  314.   assert(c == a);
  315.   assert(c <= a);
  316.   c.del(a(a.first()));
  317.   assert(c <= a);
  318.   assert(c != a);
  319.   Pix i = a.first();
  320.   assert(!c.contains(a(i)));
  321.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  322.   c.add(a(a.first()));
  323.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  324.   c |= b;
  325.   assert(b <= c);
  326.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  327.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  328.   c &= a;
  329.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  330.   c -= a;
  331.   assert(!(a <= c));
  332.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  333.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  334.   assert(c.empty());
  335.   assert(a.OK());
  336.   assert(b.OK());
  337.   assert(c.OK());
  338.  
  339.   generictest(a, b, c);
  340. }
  341.  
  342. #include "iCHSet.h"
  343.  
  344. void CHtest()
  345. {
  346.   intCHSet a(SIZE);
  347.   add(nums, a);
  348.   assert(a.length() == SIZE);
  349.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  350.   intCHSet b(SIZE);
  351.   add(odds, b);
  352.   assert(b.length() == SIZE);
  353.   intCHSet c(SIZE);
  354.   add(dups, c); 
  355.   assert(c.length() == SIZE/2);
  356.   assert(c <= a);
  357.   intCHSet d(a);
  358.   d &= b;
  359.   cout << "a: "; printset(a);
  360.   cout << "b: "; printset(b);
  361.   cout << "c: "; printset(c);
  362.   cout << "d: "; printset(d);
  363.   assert(d.length() == SIZE/2);
  364.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  365.   a.del(1);
  366.   assert(a.length() == SIZE-1);
  367.   assert(!a.contains(1));
  368.  
  369.   c.clear();
  370.   assert(c.empty());
  371.   c |= a;
  372.   assert(c == a);
  373.   assert(c <= a);
  374.   c.del(a(a.first()));
  375.   assert(c <= a);
  376.   assert(c != a);
  377.   Pix i = a.first();
  378.   assert(!c.contains(a(i)));
  379.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  380.   c.add(a(a.first()));
  381.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  382.   c |= b;
  383.   assert(b <= c);
  384.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  385.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  386.   c &= a;
  387.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  388.   c -= a;
  389.   assert(!(a <= c));
  390.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  391.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  392.   assert(c.empty());
  393.   assert(a.OK());
  394.   assert(b.OK());
  395.   assert(c.OK());
  396.  
  397.   generictest(a, b, c);
  398. }
  399.  
  400. #include "iOXPSet.h"
  401.  
  402. void OXPtest()
  403. {
  404.   intOXPSet a(SIZE);
  405.   add(nums, a);
  406.   assert(a.length() == SIZE);
  407.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  408.   intOXPSet b(SIZE);
  409.   add(odds, b);
  410.   assert(b.length() == SIZE);
  411.   intOXPSet c(SIZE);
  412.   add(dups, c); 
  413.   assert(c.length() == SIZE/2);
  414.   assert(c <= a);
  415.   intOXPSet d(a);
  416.   d &= b;
  417.   cout << "a: "; printset(a);
  418.   cout << "b: "; printset(b);
  419.   cout << "c: "; printset(c);
  420.   cout << "d: "; printset(d);
  421.   assert(d.length() == SIZE/2);
  422.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  423.   a.del(1);
  424.   assert(a.length() == SIZE-1);
  425.   assert(!a.contains(1));
  426.  
  427.   c.clear();
  428.   assert(c.empty());
  429.   c |= a;
  430.   assert(c == a);
  431.   assert(c <= a);
  432.   c.del(a(a.first()));
  433.   assert(c <= a);
  434.   assert(c != a);
  435.   Pix i = a.first();
  436.   assert(!c.contains(a(i)));
  437.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  438.   c.add(a(a.first()));
  439.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  440.   c |= b;
  441.   assert(b <= c);
  442.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  443.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  444.   c &= a;
  445.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  446.   c -= a;
  447.   assert(!(a <= c));
  448.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  449.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  450.   assert(c.empty());
  451.   assert(a.OK());
  452.   assert(b.OK());
  453.   assert(c.OK());
  454.  
  455.   generictest(a, b, c);
  456. }
  457.  
  458.  
  459.  
  460. #include "iOSLSet.h"
  461.  
  462. void OSLtest()
  463. {
  464.   intOSLSet a;
  465.   add(nums, a);
  466.   assert(a.length() == SIZE);
  467.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  468.   intOSLSet b;
  469.   add(odds, b);
  470.   assert(b.length() == SIZE);
  471.   intOSLSet c;
  472.   add(dups, c); 
  473.   assert(c.length() == SIZE/2);
  474.   assert(c <= a);
  475.   intOSLSet d(a);
  476.   d &= b;
  477.   cout << "a: "; printset(a);
  478.   cout << "b: "; printset(b);
  479.   cout << "c: "; printset(c);
  480.   cout << "d: "; printset(d);
  481.   assert(d.length() == SIZE/2);
  482.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  483.   a.del(1);
  484.   assert(a.length() == SIZE-1);
  485.   assert(!a.contains(1));
  486.  
  487.   c.clear();
  488.   assert(c.empty());
  489.   c |= a;
  490.   assert(c == a);
  491.   assert(c <= a);
  492.   c.del(a(a.first()));
  493.   assert(c <= a);
  494.   assert(c != a);
  495.   Pix i = a.first();
  496.   assert(!c.contains(a(i)));
  497.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  498.   c.add(a(a.first()));
  499.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  500.   c |= b;
  501.   assert(b <= c);
  502.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  503.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  504.   c &= a;
  505.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  506.   c -= a;
  507.   assert(!(a <= c));
  508.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  509.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  510.   assert(c.empty());
  511.   assert(a.OK());
  512.   assert(b.OK());
  513.   assert(c.OK());
  514.  
  515.   generictest(a, b, c);
  516. }
  517.  
  518. #include "iBSTSet.h"
  519.  
  520. void BSTtest()
  521. {
  522.   intBSTSet a;
  523.   add(nums, a);
  524.   assert(a.length() == SIZE);
  525.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  526.   a.balance();
  527.   assert(a.OK());
  528.   for ( j = 1; j <= SIZE; ++j) assert(a.contains(j));
  529.   intBSTSet b;
  530.   add(odds, b);
  531.   assert(b.length() == SIZE);
  532.   intBSTSet c;
  533.   add(dups, c); 
  534.   assert(c.length() == SIZE/2);
  535.   assert(c <= a);
  536.   intBSTSet d(a);
  537.   d &= b;
  538.   cout << "a: "; printset(a);
  539.   cout << "b: "; printset(b);
  540.   cout << "c: "; printset(c);
  541.   cout << "d: "; printset(d);
  542.   assert(d.length() == SIZE/2);
  543.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  544.   a.del(1);
  545.   assert(a.length() == SIZE-1);
  546.   assert(!a.contains(1));
  547.  
  548.   c.clear();
  549.   assert(c.empty());
  550.   c |= a;
  551.   assert(c == a);
  552.   assert(c <= a);
  553.   c.del(a(a.first()));
  554.   assert(c <= a);
  555.   assert(c != a);
  556.   Pix i = a.first();
  557.   assert(!c.contains(a(i)));
  558.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  559.   c.add(a(a.first()));
  560.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  561.   c |= b;
  562.   assert(b <= c);
  563.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  564.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  565.   c &= a;
  566.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  567.   c -= a;
  568.   assert(!(a <= c));
  569.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  570.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  571.   assert(c.empty());
  572.   assert(a.OK());
  573.   assert(b.OK());
  574.   assert(c.OK());
  575.  
  576.   generictest(a, b, c);
  577. }
  578.  
  579. #include "iAVLSet.h"
  580.  
  581. void AVLtest()
  582. {
  583.   intAVLSet a;
  584.   add(nums, a);
  585.   assert(a.length() == SIZE);
  586.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  587.   intAVLSet b;
  588.   add(odds, b);
  589.   assert(b.length() == SIZE);
  590.   intAVLSet c;
  591.   add(dups, c); 
  592.   assert(c.length() == SIZE/2);
  593.   assert(c <= a);
  594.   intAVLSet d(a);
  595.   d &= b;
  596.   cout << "a: "; printset(a);
  597.   cout << "b: "; printset(b);
  598.   cout << "c: "; printset(c);
  599.   cout << "d: "; printset(d);
  600.   assert(d.length() == SIZE/2);
  601.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  602.   a.del(1);
  603.   assert(a.length() == SIZE-1);
  604.   assert(!a.contains(1));
  605.  
  606.   c.clear();
  607.   assert(c.empty());
  608.   c |= a;
  609.   assert(c == a);
  610.   assert(c <= a);
  611.   c.del(a(a.first()));
  612.   assert(c <= a);
  613.   assert(c != a);
  614.   Pix i = a.first();
  615.   assert(!c.contains(a(i)));
  616.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  617.   c.add(a(a.first()));
  618.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  619.   c |= b;
  620.   assert(b <= c);
  621.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  622.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  623.   c &= a;
  624.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  625.   c -= a;
  626.   assert(!(a <= c));
  627.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  628.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  629.   assert(c.empty());
  630.   assert(a.OK());
  631.   assert(b.OK());
  632.   assert(c.OK());
  633.  
  634.   generictest(a, b, c);
  635. }
  636.  
  637. #include "iSplaySet.h"
  638.  
  639. void Splaytest()
  640. {
  641.   intSplaySet a;
  642.   add(nums, a);
  643.   assert(a.length() == SIZE);
  644.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  645.   intSplaySet b;
  646.   add(odds, b);
  647.   assert(b.length() == SIZE);
  648.   intSplaySet c;
  649.   add(dups, c); 
  650.   assert(c.length() == SIZE/2);
  651.   assert(c <= a);
  652.   intSplaySet d(a);
  653.   d &= b;
  654.   cout << "a: "; printset(a);
  655.   cout << "b: "; printset(b);
  656.   cout << "c: "; printset(c);
  657.   cout << "d: "; printset(d);
  658.   assert(d.length() == SIZE/2);
  659.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  660.   a.del(1);
  661.   assert(a.length() == SIZE-1);
  662.   assert(!a.contains(1));
  663.  
  664.   c.clear();
  665.   assert(c.empty());
  666.   c |= a;
  667.   assert(c == a);
  668.   assert(c <= a);
  669.   c.del(a(a.first()));
  670.   assert(c <= a);
  671.   assert(c != a);
  672.   Pix i = a.first();
  673.   assert(!c.contains(a(i)));
  674.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  675.   c.add(a(a.first()));
  676.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  677.   c |= b;
  678.   assert(b <= c);
  679.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  680.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  681.   c &= a;
  682.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  683.   c -= a;
  684.   assert(!(a <= c));
  685.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  686.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  687.   assert(c.empty());
  688.   assert(a.OK());
  689.   assert(b.OK());
  690.   assert(c.OK());
  691.  
  692.   generictest(a, b, c);
  693. }
  694.  
  695.  
  696. int main(int argc, char** argv)
  697. {
  698.   if (argc > 1)
  699.   {
  700.     SIZE = abs(atoi(argv[1]));
  701.     SIZE &= ~1;
  702.   }
  703.   else
  704.     SIZE = 100;
  705.   nums = new int[SIZE];
  706.   odds = new int[SIZE];
  707.   dups = new int[SIZE];
  708.   makenums();
  709.   makeodds();
  710.   makedups();
  711.   start_timer();
  712.   cout << "VHtest\n"; VHtest();
  713.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  714.   start_timer();
  715.   cout << "VOHtest\n"; VOHtest();
  716.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  717.   start_timer();
  718.   cout << "CHtest\n"; CHtest();
  719.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  720.   start_timer();
  721.   cout << "SLtest\n"; SLtest();
  722.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  723.   start_timer();
  724.   cout << "XPtest\n"; XPtest();
  725.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  726.   start_timer();
  727.   cout << "OXPtest\n"; OXPtest();
  728.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  729.   start_timer();
  730.   cout << "OSLtest\n"; OSLtest();
  731.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  732.   start_timer();
  733.   cout << "BSTtest\n"; BSTtest();
  734.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  735.   start_timer();
  736.   cout << "AVLtest\n"; AVLtest();
  737.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  738.   start_timer();
  739.   cout << "Splaytest\n"; Splaytest();
  740.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  741.  
  742.   return 0;
  743. }
  744.